package leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * Leetcode496【下一个更大元素 I】
 * https://leetcode-cn.com/problems/next-greater-element-i/
 */
public class NextBiggerElementOneFunTwo {
    private Stack<Integer> stack = new Stack<>();
    private Map<Integer , Integer> map = new HashMap<>();//用于记录每个元素的下一个更大元素
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        for (int i = nums2.length - 1; i >= 0; i--) {//循环nums2找到每个元素的下一个更大元素
            while (!stack.isEmpty() && stack.peek() <= nums2[i]){//while走完找到下一个更大元素或者当stack为空时没有更大的;栈为空判断是isEmpty不是null
                stack.pop();
            }
            int nextGreaterNum = stack.isEmpty() ? -1 : stack.peek();//这里一定要stack判空，如果为空没有更大元素
            stack.push(nums2[i]);
            map.put(nums2[i] , nextGreaterNum);//记录当前元素个下一个更大元素
        }
        int[] ret = new int[nums1.length];
        for (int i = 0; i < ret.length; i++) {//nums1中的元素nums2都有所以一定能找到对应的值
            ret[i] = map.get(nums1[i]);
        }
        return ret;
    }
}

